package com.sicheng.lc.lc笔试.网易篇;

import java.util.*;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/20 21:27
 */
public class 删数 {
    /**
     * 两个正整数a，b；每次选择删除这两个数中的一个数位，使得a是b的倍数或者b是a的倍数。
     * 问最少要操作几次。如 a = 1246，b = 9；可以删除a的一个数位得到126，是9的倍数，因此最少操作一次。
     */


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        if (ok(a, b)) {
            System.out.println(0);
            return;
        }
        int n = cnt(a) + cnt(b);
        List<Integer> A = bfs(a);
        List<Integer> B = bfs(b);
        int res = 0x3ff;
        // 其实这个过程利用数位来暴力求解 类似的数位dp也是利用每一位只能取[0,9]来枚举暴力
        // 由于数位在10以内所以这种暴力是很不暴力的
        // 比如 x是一个10位数 那么 所有可能的路径才50种 最后的运算次数最多： 50*50*10
        // bfs是O(logN^2)  总复杂度是 (logN)^4
        for (int x : A) {
            for (int y : B) {
                if (ok(x, y)) {
                    int m = cnt(x) + cnt(y);
                    res = Math.min(res, n - m);
                }
            }
        }

        System.out.println(res);
    }

    private static int cnt(int k) {
        if (k == 0)
            return 1;
        int c = 0;
        while (k != 0) {
            k /= 10;
            c++;
        }
        return c;
    }

    static boolean ok(int a, int b) {
        return Math.min(a, b) == gcd(a, b);
    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    // 枚举 x 所有的情况或者说x 有n位 x的路径子集
    // 路径子集是我自己方便理解这么叫的 官方应该没这个说法
    //  1246
    //  1-> 2,4,6
    //  2-> 4,6
    //  4-> 6
    //  6-> null   x=1246时所有路径: 1,12,14,16,146,124,126,1246,2,24,26,246,4,46,6
    static List<Integer> bfs(int x) {
        List<Integer> nums = bit(x);
        ArrayDeque<int[]> q = new ArrayDeque<>();
        List<Integer>[] g = new List[nums.size()];
        Arrays.setAll(g, k -> new ArrayList<>(10));

        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                g[i].add(j);
            }
        }

        ArrayList<Integer> list = new ArrayList<>(10);
        for (int i = 0; i < nums.size(); i++) {
            q.offer(new int[]{i, nums.get(i)});
            list.add(nums.get(i));
        }

        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] p = q.poll();
                int a = p[0];

                for (int b : g[a]) {
                    int mask = p[1] * 10 + nums.get(b);
                    q.offer(new int[]{b, mask});
                    list.add(mask);
                }
            }
        }

        return list;


    }

    // 把x 里每一位抠出来
    static List<Integer> bit(int x) {
        ArrayList<Integer> nums = new ArrayList<>();
        while (x != 0) {
            nums.add(x % 10);
            x /= 10;
        }
        Collections.reverse(nums);
        return nums;
    }
}
